home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / cool.lha / ice / pisces / flex / dfa.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-09-04  |  22.3 KB  |  970 lines
  1. /* dfa - DFA construction routines */
  2.  
  3. /*
  4.  * Copyright (c) 1989 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant to
  11.  * contract no. DE-AC03-76SF00098 between the United States Department of
  12.  * Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted
  15.  * provided that the above copyright notice and this paragraph are
  16.  * duplicated in all such forms and that any documentation,
  17.  * advertising materials, and other materials related to such
  18.  * distribution and use acknowledge that the software was developed
  19.  * by the University of California, Berkeley.  The name of the
  20.  * University may not be used to endorse or promote products derived
  21.  * from this software without specific prior written permission.
  22.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  23.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  24.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  25.  */
  26.  
  27. #ifndef lint
  28.  
  29. static char copyright[] =
  30.     "@(#) Copyright (c) 1989 The Regents of the University of California.\n";
  31. static char CR_continuation[] = "@(#) All rights reserved.\n";
  32.  
  33. static char rcsid[] =
  34.     "@(#) $Header: /tan/u1/ice/pisces/flex/RCS/dfa.c,v 1.1 90/05/15 13:13:38 neath Exp $ (LBL)";
  35.  
  36. #endif
  37.  
  38. #include "flexdef.h"
  39.  
  40.  
  41. /* check_for_backtracking - check a DFA state for backtracking
  42.  *
  43.  * synopsis
  44.  *     int ds, state[numecs];
  45.  *     check_for_backtracking( ds, state );
  46.  *
  47.  * ds is the number of the state to check and state[] is its out-transitions,
  48.  * indexed by equivalence class, and state_rules[] is the set of rules
  49.  * associated with this state
  50.  */
  51.  
  52. check_for_backtracking( ds, state )
  53. int ds;
  54. int state[];
  55.  
  56.     {
  57.     if ( (reject && ! dfaacc[ds].dfaacc_set) || ! dfaacc[ds].dfaacc_state )
  58.     { /* state is non-accepting */
  59.     ++num_backtracking;
  60.  
  61.     if ( backtrack_report )
  62.         {
  63.         fprintf( backtrack_file, "State #%d is non-accepting -\n", ds );
  64.  
  65.         /* identify the state */
  66.         dump_associated_rules( backtrack_file, ds );
  67.  
  68.         /* now identify it further using the out- and jam-transitions */
  69.         dump_transitions( backtrack_file, state );
  70.  
  71.         putc( '\n', backtrack_file );
  72.         }
  73.     }
  74.     }
  75.  
  76.  
  77. /* check_trailing_context - check to see if NFA state set constitutes
  78.  *                          "dangerous" trailing context
  79.  *
  80.  * synopsis
  81.  *    int nfa_states[num_states+1], num_states;
  82.  *    int accset[nacc+1], nacc;
  83.  *    int check_trailing_context();
  84.  *    true/false = check_trailing_context( nfa_states, num_states,
  85.  *                                         accset, nacc );
  86.  *
  87.  * NOTES
  88.  *    Trailing context is "dangerous" if both the head and the trailing
  89.  *  part are of variable size \and/ there's a DFA state which contains
  90.  *  both an accepting state for the head part of the rule and NFA states
  91.  *  which occur after the beginning of the trailing context.
  92.  *  When such a rule is matched, it's impossible to tell if having been
  93.  *  in the DFA state indicates the beginning of the trailing context
  94.  *  or further-along scanning of the pattern.  In these cases, a warning
  95.  *  message is issued.
  96.  *
  97.  *    nfa_states[1 .. num_states] is the list of NFA states in the DFA.
  98.  *    accset[1 .. nacc] is the list of accepting numbers for the DFA state.
  99.  */
  100.  
  101. int check_trailing_context( nfa_states, num_states, accset, nacc )
  102. int *nfa_states, num_states;
  103. int *accset;
  104. register int nacc;
  105.  
  106.     {
  107.     register int i, j;
  108.  
  109.     for ( i = 1; i <= num_states; ++i )
  110.     {
  111.     int ns = nfa_states[i];
  112.     register int type = state_type[ns];
  113.     register int ar = assoc_rule[ns];
  114.  
  115.     if ( type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE )
  116.         { /* do nothing */
  117.         }
  118.  
  119.     else if ( type == STATE_TRAILING_CONTEXT )
  120.         {
  121.         /* potential trouble.  Scan set of accepting numbers for
  122.          * the one marking the end of the "head".  We assume that
  123.          * this looping will be fairly cheap since it's rare that
  124.          * an accepting number set is large.
  125.          */
  126.         for ( j = 1; j <= nacc; ++j )
  127.         if ( accset[j] & YY_TRAILING_HEAD_MASK )
  128.             {
  129.             fprintf( stderr,
  130.              "flex: Dangerous trailing context in rule at line %d\n",
  131.                  rule_linenum[ar] );
  132.             return;
  133.             }
  134.         }
  135.     }
  136.     }
  137.  
  138.  
  139. /* dump_associated_rules - list the rules associated with a DFA state
  140.  *
  141.  * synopisis
  142.  *     int ds;
  143.  *     FILE *file;
  144.  *     dump_associated_rules( file, ds );
  145.  *
  146.  * goes through the set of NFA states associated with the DFA and
  147.  * extracts the first MAX_ASSOC_RULES unique rules, sorts them,
  148.  * and writes a report to the given file
  149.  */
  150.  
  151. dump_associated_rules( file, ds )
  152. FILE *file;
  153. int ds;
  154.  
  155.     {
  156.     register int i, j;
  157.     register int num_associated_rules = 0;
  158.     int rule_set[MAX_ASSOC_RULES + 1];
  159.     int *dset = dss[ds];
  160.     int size = dfasiz[ds];
  161.     
  162.     for ( i = 1; i <= size; ++i )
  163.     {
  164.     register rule_num = rule_linenum[assoc_rule[dset[i]]];
  165.  
  166.     for ( j = 1; j <= num_associated_rules; ++j )
  167.         if ( rule_num == rule_set[j] )
  168.         break;
  169.  
  170.     if ( j > num_associated_rules )
  171.         { /* new rule */
  172.         if ( num_associated_rules < MAX_ASSOC_RULES )
  173.         rule_set[++num_associated_rules] = rule_num;
  174.         }
  175.     }
  176.  
  177.     bubble( rule_set, num_associated_rules );
  178.  
  179.     fprintf( file, " associated rules:" );
  180.  
  181.     for ( i = 1; i <= num_associated_rules; ++i )
  182.     {
  183.     if ( i % 8 == 1 )
  184.         putc( '\n', file );
  185.     
  186.     fprintf( file, "\t%d", rule_set[i] );
  187.     }
  188.     
  189.     putc( '\n', file );
  190.     }
  191.  
  192.  
  193. /* dump_transitions - list the transitions associated with a DFA state
  194.  *
  195.  * synopisis
  196.  *     int state[numecs];
  197.  *     FILE *file;
  198.  *     dump_transitions( file, state );
  199.  *
  200.  * goes through the set of out-transitions and lists them in human-readable
  201.  * form (i.e., not as equivalence classes); also lists jam transitions
  202.  * (i.e., all those which are not out-transitions, plus EOF).  The dump
  203.  * is done to the given file.
  204.  */
  205.  
  206. dump_transitions( file, state )
  207. FILE *file;
  208. int state[];
  209.  
  210.     {
  211.     register int i, ec;
  212.     int out_char_set[CSIZE + 1];
  213.  
  214.     for ( i = 1; i <= CSIZE; ++i )
  215.     {
  216.     ec = ecgroup[i];
  217.  
  218.     if ( ec < 0 )
  219.         ec = -ec;
  220.  
  221.     out_char_set[i] = state[ec];
  222.     }
  223.     
  224.     fprintf( file, " out-transitions: " );
  225.  
  226.     list_character_set( file, out_char_set );
  227.  
  228.     /* now invert the members of the set to get the jam transitions */
  229.     for ( i = 1; i <= CSIZE; ++i )
  230.     out_char_set[i] = ! out_char_set[i];
  231.  
  232.     fprintf( file, "\n jam-transitions: EOF " );
  233.  
  234.     list_character_set( file, out_char_set );
  235.  
  236.     putc( '\n', file );
  237.     }
  238.  
  239.  
  240. /* epsclosure - construct the epsilon closure of a set of ndfa states
  241.  *
  242.  * synopsis
  243.  *    int t[current_max_dfa_size], numstates, accset[num_rules + 1], nacc;
  244.  *    int hashval;
  245.  *    int *epsclosure();
  246.  *    t = epsclosure( t, &numstates, accset, &nacc, &hashval );
  247.  *
  248.  * NOTES
  249.  *    the epsilon closure is the set of all states reachable by an arbitrary
  250.  *  number of epsilon transitions which themselves do not have epsilon
  251.  *  transitions going out, unioned with the set of states which have non-null
  252.  *  accepting numbers.  t is an array of size numstates of nfa state numbers.
  253.  *  Upon return, t holds the epsilon closure and numstates is updated.  accset
  254.  *  holds a list of the accepting numbers, and the size of accset is given
  255.  *  by nacc.  t may be subjected to reallocation if it is not large enough
  256.  *  to hold the epsilon closure.
  257.  *
  258.  *    hashval is the hash value for the dfa corresponding to the state set
  259.  */
  260.  
  261. int *epsclosure( t, ns_addr, accset, nacc_addr, hv_addr )
  262. int *t, *ns_addr, accset[], *nacc_addr, *hv_addr;
  263.  
  264.     {
  265.     register int stkpos, ns, tsp;
  266.     int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum;
  267.     int stkend, nstate;
  268.     static int did_stk_init = false, *stk; 
  269.  
  270. #define MARK_STATE(state) \
  271.     trans1[state] = trans1[state] - MARKER_DIFFERENCE;
  272.  
  273. #define IS_MARKED(state) (trans1[state] < 0)
  274.  
  275. #define UNMARK_STATE(state) \
  276.     trans1[state] = trans1[state] + MARKER_DIFFERENCE;
  277.  
  278. #define CHECK_ACCEPT(state) \
  279.     { \
  280.     nfaccnum = accptnum[state]; \
  281.     if ( nfaccnum != NIL ) \
  282.         accset[++nacc] = nfaccnum; \
  283.     }
  284.  
  285. #define DO_REALLOCATION \
  286.     { \
  287.     current_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \
  288.     ++num_reallocs; \
  289.     t = reallocate_integer_array( t, current_max_dfa_size ); \
  290.     stk = reallocate_integer_array( stk, current_max_dfa_size ); \
  291.     } \
  292.  
  293. #define PUT_ON_STACK(state) \
  294.     { \
  295.     if ( ++stkend >= current_max_dfa_size ) \
  296.         DO_REALLOCATION \
  297.     stk[stkend] = state; \
  298.     MARK_STATE(state) \
  299.     }
  300.  
  301. #define ADD_STATE(state) \
  302.     { \
  303.     if ( ++numstates >= current_max_dfa_size ) \
  304.         DO_REALLOCATION \
  305.     t[numstates] = state; \
  306.     hashval = hashval + state; \
  307.     }
  308.  
  309. #define STACK_STATE(state) \
  310.     { \
  311.     PUT_ON_STACK(state) \
  312.     CHECK_ACCEPT(state) \
  313.     if ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \
  314.         ADD_STATE(state) \
  315.     }
  316.  
  317.     if ( ! did_stk_init )
  318.     {
  319.     stk = allocate_integer_array( current_max_dfa_size );
  320.     did_stk_init = true;
  321.     }
  322.  
  323.     nacc = stkend = hashval = 0;
  324.  
  325.     for ( nstate = 1; nstate <= numstates; ++nstate )
  326.     {
  327.     ns = t[nstate];
  328.  
  329.     /* the state could be marked if we've already pushed it onto
  330.      * the stack
  331.      */
  332.     if ( ! IS_MARKED(ns) )
  333.         PUT_ON_STACK(ns)
  334.  
  335.     CHECK_ACCEPT(ns)
  336.     hashval = hashval + ns;
  337.     }
  338.  
  339.     for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  340.     {
  341.     ns = stk[stkpos];
  342.     transsym = transchar[ns];
  343.  
  344.     if ( transsym == SYM_EPSILON )
  345.         {
  346.         tsp = trans1[ns] + MARKER_DIFFERENCE;
  347.  
  348.         if ( tsp != NO_TRANSITION )
  349.         {
  350.         if ( ! IS_MARKED(tsp) )
  351.             STACK_STATE(tsp)
  352.  
  353.         tsp = trans2[ns];
  354.  
  355.         if ( tsp != NO_TRANSITION )
  356.             if ( ! IS_MARKED(tsp) )
  357.             STACK_STATE(tsp)
  358.         }
  359.         }
  360.     }
  361.  
  362.     /* clear out "visit" markers */
  363.  
  364.     for ( stkpos = 1; stkpos <= stkend; ++stkpos )
  365.     {
  366.     if ( IS_MARKED(stk[stkpos]) )
  367.         {
  368.         UNMARK_STATE(stk[stkpos])
  369.         }
  370.     else
  371.         flexfatal( "consistency check failed in epsclosure()" );
  372.     }
  373.  
  374.     *ns_addr = numstates;
  375.     *hv_addr = hashval;
  376.     *nacc_addr = nacc;
  377.  
  378.     return ( t );
  379.     }
  380.  
  381.  
  382. /* increase_max_dfas - increase the maximum number of DFAs */
  383.  
  384. increase_max_dfas()
  385.  
  386.     {
  387.     current_max_dfas += MAX_DFAS_INCREMENT;
  388.  
  389.     ++num_reallocs;
  390.  
  391.     base = reallocate_integer_array( base, current_max_dfas );
  392.     def = reallocate_integer_array( def, current_max_dfas );
  393.     dfasiz = reallocate_integer_array( dfasiz, current_max_dfas );
  394.     accsiz = reallocate_integer_array( accsiz, current_max_dfas );
  395.     dhash = reallocate_integer_array( dhash, current_max_dfas );
  396.     dss = reallocate_int_ptr_array( dss, current_max_dfas );
  397.     dfaacc = reallocate_dfaacc_union( dfaacc, current_max_dfas );
  398.     }
  399.  
  400.  
  401. /* ntod - convert an ndfa to a dfa
  402.  *
  403.  * synopsis
  404.  *    ntod();
  405.  *
  406.  *  creates the dfa corresponding to the ndfa we've constructed.  the
  407.  *  dfa starts out in state #1.
  408.  */
  409. ntod()
  410.  
  411.     {
  412.     int *accset, ds, nacc, newds;
  413.     int duplist[CSIZE + 1], sym, hashval, numstates, dsize;
  414.     int targfreq[CSIZE + 1], targstate[CSIZE + 1], state[CSIZE + 1];
  415.     int *nset, *dset;
  416.     int targptr, totaltrans, i, comstate, comfreq, targ;
  417.     int *epsclosure(), snstods(), symlist[CSIZE + 1];
  418.     int num_start_states;
  419.     int todo_head, todo_next;
  420.  
  421.     /* this is so find_table_space(...) will know where to start looking in
  422.      * chk/nxt for unused records for space to put in the state
  423.      */
  424.     if ( fullspd )
  425.     firstfree = 0;
  426.  
  427.     accset = allocate_integer_array( num_rules + 1 );
  428.     nset = allocate_integer_array( current_max_dfa_size );
  429.  
  430.     /* the "todo" queue is represented by the head, which is the DFA
  431.      * state currently being processed, and the "next", which is the
  432.      * next DFA state number available (not in use).  We depend on the
  433.      * fact that snstods() returns DFA's \in increasing order/, and thus
  434.      * need only know the bounds of the dfas to be processed.
  435.      */
  436.     todo_head = todo_next = 0;
  437.  
  438.     for ( i = 0; i <= CSIZE; ++i )
  439.     {
  440.     duplist[i] = NIL;
  441.     symlist[i] = false;
  442.     }
  443.  
  444.     for ( i = 0; i <= num_rules; ++i )
  445.     accset[i] = NIL;
  446.  
  447.     if ( trace )
  448.     {
  449.     dumpnfa( scset[1] );
  450.     fputs( "\n\nDFA Dump:\n\n", stderr );
  451.     }
  452.  
  453.     inittbl();
  454.  
  455.     if ( fullspd )
  456.     {
  457.     for ( i = 0; i <= numecs; ++i )
  458.         state[i] = 0;
  459.     place_state( state, 0, 0 );
  460.     }
  461.  
  462.     if ( fulltbl )
  463.     {
  464.     /* declare it "short" because it's a real long-shot that that
  465.      * won't be large enough
  466.      */
  467.     printf( "static short int %s[][%d] =\n    {\n", NEXTARRAY,
  468.         numecs + 1 ); /* '}' so vi doesn't get too confused */
  469.  
  470.     /* generate 0 entries for state #0 */
  471.     for ( i = 0; i <= numecs; ++i )
  472.         mk2data( 0 );
  473.  
  474.     /* force ',' and dataflush() next call to mk2data */
  475.     datapos = NUMDATAITEMS;
  476.  
  477.     /* force extra blank line next dataflush() */
  478.     dataline = NUMDATALINES;
  479.     }
  480.  
  481.     /* create the first states */
  482.  
  483.     num_start_states = lastsc * 2;
  484.  
  485.     for ( i = 1; i <= num_start_states; ++i )
  486.     {
  487.     numstates = 1;
  488.  
  489.     /* for each start condition, make one state for the case when
  490.      * we're at the beginning of the line (the '%' operator) and
  491.      * one for the case when we're not
  492.      */
  493.     if ( i % 2 == 1 )
  494.         nset[numstates] = scset[(i / 2) + 1];
  495.     else
  496.         nset[numstates] = mkbranch( scbol[i / 2], scset[i / 2] );
  497.  
  498.     nset = epsclosure( nset, &numstates, accset, &nacc, &hashval );
  499.  
  500.     if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) )
  501.         {
  502.         numas += nacc;
  503.         totnst += numstates;
  504.         ++todo_next;
  505.  
  506.         if ( variable_trailing_context_rules && nacc > 0 )
  507.         check_trailing_context( nset, numstates, accset, nacc );
  508.         }
  509.     }
  510.  
  511.     if ( ! fullspd )
  512.     {
  513.     if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )
  514.         flexfatal( "could not create unique end-of-buffer state" );
  515.  
  516.     ++numas;
  517.     ++num_start_states;
  518.     ++todo_next;
  519.     }
  520.  
  521.     while ( todo_head < todo_next )
  522.     {
  523.     targptr = 0;
  524.     totaltrans = 0;
  525.  
  526.     for ( i = 1; i <= numecs; ++i )
  527.         state[i] = 0;
  528.  
  529.     ds = ++todo_head;
  530.  
  531.     dset = dss[ds];
  532.     dsize = dfasiz[ds];
  533.  
  534.     if ( trace )
  535.         fprintf( stderr, "state # %d:\n", ds );
  536.  
  537.     sympartition( dset, dsize, symlist, duplist );
  538.  
  539.     for ( sym = 1; sym <= numecs; ++sym )
  540.         {
  541.         if ( symlist[sym] )
  542.         {
  543.         symlist[sym] = 0;
  544.  
  545.         if ( duplist[sym] == NIL )
  546.             { /* symbol has unique out-transitions */
  547.             numstates = symfollowset( dset, dsize, sym, nset );
  548.             nset = epsclosure( nset, &numstates, accset,
  549.                        &nacc, &hashval );
  550.  
  551.             if ( snstods( nset, numstates, accset,
  552.                   nacc, hashval, &newds ) )
  553.             {
  554.             totnst = totnst + numstates;
  555.             ++todo_next;
  556.             numas += nacc;
  557.  
  558.             if ( variable_trailing_context_rules && nacc > 0 )
  559.                 check_trailing_context( nset, numstates,
  560.                 accset, nacc );
  561.             }
  562.  
  563.             state[sym] = newds;
  564.  
  565.             if ( trace )
  566.             fprintf( stderr, "\t%d\t%d\n", sym, newds );
  567.  
  568.             targfreq[++targptr] = 1;
  569.             targstate[targptr] = newds;
  570.             ++numuniq;
  571.             }
  572.  
  573.         else
  574.             {
  575.             /* sym's equivalence class has the same transitions
  576.              * as duplist(sym)'s equivalence class
  577.              */
  578.             targ = state[duplist[sym]];
  579.             state[sym] = targ;
  580.  
  581.             if ( trace )
  582.             fprintf( stderr, "\t%d\t%d\n", sym, targ );
  583.  
  584.             /* update frequency count for destination state */
  585.  
  586.             i = 0;
  587.             while ( targstate[++i] != targ )
  588.             ;
  589.  
  590.             ++targfreq[i];
  591.             ++numdup;
  592.             }
  593.  
  594.         ++totaltrans;
  595.         duplist[sym] = NIL;
  596.         }
  597.         }
  598.  
  599.     numsnpairs = numsnpairs + totaltrans;
  600.  
  601.     if ( caseins && ! useecs )
  602.         {
  603.         register int j;
  604.  
  605.         for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
  606.         state[i] = state[j];
  607.         }
  608.  
  609.     if ( ds > num_start_states )
  610.         check_for_backtracking( ds, state );
  611.  
  612.     if ( fulltbl )
  613.         {
  614.         /* supply array's 0-element */
  615.         if ( ds == end_of_buffer_state )
  616.         mk2data( -end_of_buffer_state );
  617.         else
  618.         mk2data( end_of_buffer_state );
  619.  
  620.         for ( i = 1; i <= numecs; ++i )
  621.         /* jams are marked by negative of state number */
  622.         mk2data( state[i] ? state[i] : -ds );
  623.  
  624.         /* force ',' and dataflush() next call to mk2data */
  625.         datapos = NUMDATAITEMS;
  626.  
  627.         /* force extra blank line next dataflush() */
  628.         dataline = NUMDATALINES;
  629.         }
  630.  
  631.         else if ( fullspd )
  632.         place_state( state, ds, totaltrans );
  633.  
  634.     else if ( ds == end_of_buffer_state )
  635.         /* special case this state to make sure it does what it's
  636.          * supposed to, i.e., jam on end-of-buffer
  637.          */
  638.         stack1( ds, 0, 0, JAMSTATE );
  639.  
  640.     else /* normal, compressed state */
  641.         {
  642.         /* determine which destination state is the most common, and
  643.          * how many transitions to it there are
  644.          */
  645.  
  646.         comfreq = 0;
  647.         comstate = 0;
  648.  
  649.         for ( i = 1; i <= targptr; ++i )
  650.         if ( targfreq[i] > comfreq )
  651.             {
  652.             comfreq = targfreq[i];
  653.             comstate = targstate[i];
  654.             }
  655.  
  656.         bldtbl( state, ds, totaltrans, comstate, comfreq );
  657.         }
  658.     }
  659.  
  660.     if ( fulltbl )
  661.     dataend();
  662.  
  663.     else if ( ! fullspd )
  664.     {
  665.     cmptmps();  /* create compressed template entries */
  666.  
  667.     /* create tables for all the states with only one out-transition */
  668.     while ( onesp > 0 )
  669.         {
  670.         mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp],
  671.             onedef[onesp] );
  672.         --onesp;
  673.         }
  674.  
  675.     mkdeftbl();
  676.     }
  677.     }
  678.  
  679.  
  680. /* snstods - converts a set of ndfa states into a dfa state
  681.  *
  682.  * synopsis
  683.  *    int sns[numstates], numstates, newds, accset[num_rules + 1], nacc, hashval;
  684.  *    int snstods();
  685.  *    is_new_state = snstods( sns, numstates, accset, nacc, hashval, &newds );
  686.  *
  687.  * on return, the dfa state number is in newds.
  688.  */
  689.  
  690. int snstods( sns, numstates, accset, nacc, hashval, newds_addr )
  691. int sns[], numstates, accset[], nacc, hashval, *newds_addr;
  692.  
  693.     {
  694.     int didsort = 0;
  695.     register int i, j;
  696.     int newds, *oldsns;
  697.     char *malloc();
  698.  
  699.     for ( i = 1; i <= lastdfa; ++i )
  700.     if ( hashval == dhash[i] )
  701.         {
  702.         if ( numstates == dfasiz[i] )
  703.         {
  704.         oldsns = dss[i];
  705.  
  706.         if ( ! didsort )
  707.             {
  708.             /* we sort the states in sns so we can compare it to
  709.              * oldsns quickly.  we use bubble because there probably
  710.              * aren't very many states
  711.              */
  712.             bubble( sns, numstates );
  713.             didsort = 1;
  714.             }
  715.  
  716.         for ( j = 1; j <= numstates; ++j )
  717.             if ( sns[j] != oldsns[j] )
  718.             break;
  719.  
  720.         if ( j > numstates )
  721.             {
  722.             ++dfaeql;
  723.             *newds_addr = i;
  724.             return ( 0 );
  725.             }
  726.  
  727.         ++hshcol;
  728.         }
  729.  
  730.         else
  731.         ++hshsave;
  732.         }
  733.  
  734.     /* make a new dfa */
  735.  
  736.     if ( ++lastdfa >= current_max_dfas )
  737.     increase_max_dfas();
  738.  
  739.     newds = lastdfa;
  740.  
  741.     dss[newds] = (int *) malloc( (unsigned) ((numstates + 1) * sizeof( int )) );
  742.  
  743.     if ( ! dss[newds] )
  744.     flexfatal( "dynamic memory failure in snstods()" );
  745.  
  746.     /* if we haven't already sorted the states in sns, we do so now, so that
  747.      * future comparisons with it can be made quickly
  748.      */
  749.  
  750.     if ( ! didsort )
  751.     bubble( sns, numstates );
  752.  
  753.     for ( i = 1; i <= numstates; ++i )
  754.     dss[newds][i] = sns[i];
  755.  
  756.     dfasiz[newds] = numstates;
  757.     dhash[newds] = hashval;
  758.  
  759.     if ( nacc == 0 )
  760.     {
  761.     if ( reject )
  762.         dfaacc[newds].dfaacc_set = (int *) 0;
  763.     else
  764.         dfaacc[newds].dfaacc_state = 0;
  765.  
  766.     accsiz[newds] = 0;
  767.     }
  768.  
  769.     else if ( reject )
  770.     {
  771.     /* we sort the accepting set in increasing order so the disambiguating
  772.      * rule that the first rule listed is considered match in the event of
  773.      * ties will work.  We use a bubble sort since the list is probably
  774.      * quite small.
  775.      */
  776.  
  777.     bubble( accset, nacc );
  778.  
  779.     dfaacc[newds].dfaacc_set =
  780.         (int *) malloc( (unsigned) ((nacc + 1) * sizeof( int )) );
  781.  
  782.     if ( ! dfaacc[newds].dfaacc_set )
  783.         flexfatal( "dynamic memory failure in snstods()" );
  784.  
  785.     /* save the accepting set for later */
  786.     for ( i = 1; i <= nacc; ++i )
  787.         dfaacc[newds].dfaacc_set[i] = accset[i];
  788.  
  789.     accsiz[newds] = nacc;
  790.     }
  791.  
  792.     else
  793.     { /* find lowest numbered rule so the disambiguating rule will work */
  794.     j = num_rules + 1;
  795.  
  796.     for ( i = 1; i <= nacc; ++i )
  797.         if ( accset[i] < j )
  798.         j = accset[i];
  799.  
  800.     dfaacc[newds].dfaacc_state = j;
  801.     }
  802.  
  803.     *newds_addr = newds;
  804.  
  805.     return ( 1 );
  806.     }
  807.  
  808.  
  809. /* symfollowset - follow the symbol transitions one step
  810.  *
  811.  * synopsis
  812.  *    int ds[current_max_dfa_size], dsize, transsym;
  813.  *    int nset[current_max_dfa_size], numstates;
  814.  *    numstates = symfollowset( ds, dsize, transsym, nset );
  815.  */
  816.  
  817. int symfollowset( ds, dsize, transsym, nset )
  818. int ds[], dsize, transsym, nset[];
  819.  
  820.     {
  821.     int ns, tsp, sym, i, j, lenccl, ch, numstates;
  822.     int ccllist;
  823.  
  824.     numstates = 0;
  825.  
  826.     for ( i = 1; i <= dsize; ++i )
  827.     { /* for each nfa state ns in the state set of ds */
  828.     ns = ds[i];
  829.     sym = transchar[ns];
  830.     tsp = trans1[ns];
  831.  
  832.     if ( sym < 0 )
  833.         { /* it's a character class */
  834.         sym = -sym;
  835.         ccllist = cclmap[sym];
  836.         lenccl = ccllen[sym];
  837.  
  838.         if ( cclng[sym] )
  839.         {
  840.         for ( j = 0; j < lenccl; ++j )
  841.             { /* loop through negated character class */
  842.             ch = ccltbl[ccllist + j];
  843.  
  844.             if ( ch > transsym )
  845.             break;    /* transsym isn't in negated ccl */
  846.  
  847.             else if ( ch == transsym )
  848.             /* next 2 */ goto bottom;
  849.             }
  850.  
  851.         /* didn't find transsym in ccl */
  852.         nset[++numstates] = tsp;
  853.         }
  854.  
  855.         else
  856.         for ( j = 0; j < lenccl; ++j )
  857.             {
  858.             ch = ccltbl[ccllist + j];
  859.  
  860.             if ( ch > transsym )
  861.             break;
  862.  
  863.             else if ( ch == transsym )
  864.             {
  865.             nset[++numstates] = tsp;
  866.             break;
  867.             }
  868.             }
  869.         }
  870.  
  871.     else if ( sym >= 'A' && sym <= 'Z' && caseins )
  872.         flexfatal( "consistency check failed in symfollowset" );
  873.  
  874.     else if ( sym == SYM_EPSILON )
  875.         { /* do nothing */
  876.         }
  877.  
  878.     else if ( ecgroup[sym] == transsym )
  879.         nset[++numstates] = tsp;
  880.  
  881. bottom:
  882.     ;
  883.     }
  884.  
  885.     return ( numstates );
  886.     }
  887.  
  888.  
  889. /* sympartition - partition characters with same out-transitions
  890.  *
  891.  * synopsis
  892.  *    integer ds[current_max_dfa_size], numstates, duplist[numecs];
  893.  *    symlist[numecs];
  894.  *    sympartition( ds, numstates, symlist, duplist );
  895.  */
  896.  
  897. sympartition( ds, numstates, symlist, duplist )
  898. int ds[], numstates, duplist[];
  899. int symlist[];
  900.  
  901.     {
  902.     int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich;
  903.  
  904.     /* partitioning is done by creating equivalence classes for those
  905.      * characters which have out-transitions from the given state.  Thus
  906.      * we are really creating equivalence classes of equivalence classes.
  907.      */
  908.  
  909.     for ( i = 1; i <= numecs; ++i )
  910.     { /* initialize equivalence class list */
  911.     duplist[i] = i - 1;
  912.     dupfwd[i] = i + 1;
  913.     }
  914.  
  915.     duplist[1] = NIL;
  916.     dupfwd[numecs] = NIL;
  917.  
  918.     for ( i = 1; i <= numstates; ++i )
  919.     {
  920.     ns = ds[i];
  921.     tch = transchar[ns];
  922.  
  923.     if ( tch != SYM_EPSILON )
  924.         {
  925.         if ( tch < -lastccl || tch > CSIZE )
  926.         flexfatal( "bad transition character detected in sympartition()" );
  927.  
  928.         if ( tch > 0 )
  929.         { /* character transition */
  930.         mkechar( ecgroup[tch], dupfwd, duplist );
  931.         symlist[ecgroup[tch]] = 1;
  932.         }
  933.  
  934.         else
  935.         { /* character class */
  936.         tch = -tch;
  937.  
  938.         lenccl = ccllen[tch];
  939.         cclp = cclmap[tch];
  940.         mkeccl( ccltbl + cclp, lenccl, dupfwd, duplist, numecs );
  941.  
  942.         if ( cclng[tch] )
  943.             {
  944.             j = 0;
  945.  
  946.             for ( k = 0; k < lenccl; ++k )
  947.             {
  948.             ich = ccltbl[cclp + k];
  949.  
  950.             for ( ++j; j < ich; ++j )
  951.                 symlist[j] = 1;
  952.             }
  953.  
  954.             for ( ++j; j <= numecs; ++j )
  955.             symlist[j] = 1;
  956.             }
  957.  
  958.         else
  959.             for ( k = 0; k < lenccl; ++k )
  960.             {
  961.             ich = ccltbl[cclp + k];
  962.             symlist[ich] = 1;
  963.             }
  964.         }
  965.         }
  966.     }
  967.     }
  968.  
  969.  
  970.